#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef enum { Link, Thread } NodeTag;

class TreeNode
{
private:
    char data;              //值
    TreeNode* leftChild;    //左孩子
    TreeNode* rightChild;   //右孩子
    NodeTag lTag, rTag;     //线索Tag

    friend class MyTree;    //树类
public:
    TreeNode(char, TreeNode*, TreeNode*, NodeTag, NodeTag);
    TreeNode(char d);
    ~TreeNode();

    void printNode();

};

class MyTree
{
private:
    TreeNode* root;        //根指针
    bool isThread;         //线索二叉树标志

    TreeNode* buildFromPreorder(const char arr[], int& index);
    void destroy(TreeNode* node);
    TreeNode* copyTree(TreeNode* node);

    void preOrder(TreeNode* node);
    void inOrder(TreeNode* node);
    void postOrder(TreeNode* node);

    int countLeaf(TreeNode* node);
    int countHeight(TreeNode* node);

    void inOrderThreading(TreeNode* node, TreeNode*& pre);

    TreeNode* locateNode(TreeNode* node, const char& v);
public:
    MyTree();               //无参构造
    MyTree(const char[]);   //构造函数
    MyTree(const MyTree&);  //拷贝函数
    ~MyTree();              //析构函数

    void preOrderTraverse();    //前序遍历
    void inOrderTraverse();     //中序遍历
    void postOrderTraverse();   //后序遍历
    int countLeaf();            //叶结点计数
    int countHeight();          //计算树的深度
    bool isThreadedTree();      //判断是否为线索二叉树
    bool inOrderThreading();    //线索化
    TreeNode& locateNode(const char&);  //结点定位
    TreeNode& preNode(const TreeNode&); //获取前驱结点
    TreeNode& nextNode(const TreeNode&);//获取后继结点

};


class HuffmanTree
{
private:
    //添加必要的数据成员
    struct HuffmanNode {
        int weight;
        HuffmanNode* left;
        HuffmanNode* right;
        HuffmanNode(int w, HuffmanNode* l = NULL, HuffmanNode* r = NULL) : weight(w), left(l), right(r) {}
    };
    HuffmanNode* root;
    vector<pair<int, string>> codes;

    void destroy(HuffmanNode* node);
    void generateCodes(HuffmanNode* node, string code);
    static bool compare(const HuffmanNode* a, const HuffmanNode* b);

public:
    HuffmanTree(const int&, const int[]);    //构造函数
    ~HuffmanTree();     //析构函数

    //输出哈夫曼编码
    //格式为：每行输出一个节点，节点排序递减
    //节点1值：编码
    //节点2值：编码
    //....
    //cpp中未给出该函数，遵守输出格式规范
    void printHuffmanCodes();


};


